// 平均值最小累加和
// 给定一个数组arr，长度为n
// 再给定一个数字k，表示一定要将arr划分成k个集合
// 每个数字只能进一个集合
// 返回每个集合的平均值都累加起来的最小值
// 平均值向下取整
// 1 <= n <= 10^5
// 0 <= arr[i] <= 10^5
// 1 <= k <= n
// 来自真实大厂笔试，没有在线测试，对数器验证

#include <bits/stdc++.h>

using namespace std;

// 暴力方法
// 为了验证
int f(vector<int>& arr, int i, vector<int>& sum, vector<int>& cnt)
{
    // 后续没数了
    if(i == arr.size())
    {
        int ans = 0;
        for(int j = 0; j < sum.size(); ++j)
        {
            if(cnt[j] == 0) return INT_MAX;
            ans += sum[j] / cnt[j];
        }
        return ans;
    }
    else
    {
        int ans = INT_MAX;
        // i 这个数进 j 集合
        for(int j = 0; j < sum.size(); ++j)
        {
            sum[j] += arr[i];
            ++cnt[j];
            ans = min(ans, f(arr, i + 1, sum, cnt));
            sum[j] -= arr[i];
            --cnt[j];
        }
        return ans;
    }
}

// 暴力方法
// 为了验证
// 每个数字做出所有可能的选择
// 时间复杂度O(k的n次方)
int minAverageSum1(vector<int>& arr, int k)
{
    vector<int> sum(k);
    vector<int> cnt(k);
    return f(arr, 0, sum, cnt);
}

// 正式方法
// 时间复杂度O(n * logn)
int minAverageSum2(vector<int>& arr, int k)
{
    sort(arr.begin(), arr.end());
    int ans = 0;
    for(int i = 0; i < k - 1; ++i)
    {
        ans += arr[i]; // 最小的k-1个数，每个数独自成一个集合
    }
    int sum = accumulate(arr.begin() + k - 1, arr.end(), 0);
    ans += sum / (arr.size() - k + 1);
    return ans;
}

// 为了测试
vector<int> randomArray(int n, int v)
{
    vector<int> ans(n);
    for(int i = 0; i < n; ++i) ans[i] = rand() % v;
    return ans;
}

// 为了测试
int main()
{   
    srand(time(nullptr));
    int N = 8;
    int V = 10000;
    int testTimes = 2000;
    cout << "测试开始" << endl;
    for(int i = 1; i <= testTimes; ++i)
    {
        int n = rand() % N + 1;
        int k = rand() % n + 1;
        vector<int> arr = randomArray(n, V);
        int ans1 = minAverageSum1(arr, k);
        int ans2 = minAverageSum2(arr, k);
        if(ans1 != ans2) cout << "出错了！" << endl;
        if(i % 100 == 0) cout << "(测试到第" << i << "组)" << endl;
    }
    cout << "测试结束" << endl;

    return 0;
}